﻿#define _CRT_SECURE_NO_WARNINGS 1
//全排列（medium）:https://leetcode.cn/problems/permutations/
class Solution
{
	vector<vector<int>> ret;
	vector<int> path;
		bool check[7];
public:
	vector<vector<int>> permute(vector<int>& nums)
	{
		dfs(nums);
		return ret;
	}
	void dfs(vector<int>& nums)
	{
		if (path.size() == nums.size())
		{
			ret.push_back(path);
			return;
		}
		for (int i = 0; i < nums.size(); i++)
		{
			if (!check[i])
			{
				path.push_back(nums[i]);
				check[i] = true;
				dfs(nums);
				// 回溯 -> 恢复现场
				path.pop_back();
				check[i] = false;
			}
		}
	}
};

//⼦集（medium）:https://leetcode.cn/problems/subsets/description/
// 解法⼀：
class Solution
{
	vector<vector<int>> ret;
	vector<int> path;
public:
	vector<vector<int>> subsets(vector<int>& nums)
	{
		dfs(nums, 0);
		return ret;
	}
	void dfs(vector<int>& nums, int pos)
	{
		if (pos == nums.size())
		{
			ret.push_back(path);
			return;
		}
		// 选
		path.push_back(nums[pos]);
		dfs(nums, pos + 1);
		path.pop_back(); // 恢复现场
		// 不选
		dfs(nums, pos + 1);
	}
};
// 解法⼆：
class Solution
{
	vector<vector<int>> ret;
	vector<int> path;
public:
	vector<vector<int>> subsets(vector<int>& nums)
	{

		dfs(nums, 0);
		return ret;
	}
	void dfs(vector<int>& nums, int pos)
	{
		ret.push_back(path);
		for (int i = pos; i < nums.size(); i++)
		{
			path.push_back(nums[i]);
			dfs(nums, i + 1);
			path.pop_back(); // 恢复现场
		}
	}
};